class Graph():
    def __init__(self,Adj,V=None):
        self.Adj=Adj
        if V is None:
            self.V=range(len(self.Adj)) #自定义顶点顺序
        else:
            self.V=V
        self.d=[None]*len(self.Adj) #bit suggesting if the node is checked in DFS
        self.vetex_order=[]
        self.k=0 #number of trees
        self.forests=[]
    def DFS(self):
        for u in self.V:
            if self.d[u] is None:
                self.k+=1
                self.forests.append([])
                self.forests[-1].append(u)
                self.DFS_visit(u)
    def DFS_visit(self,u):
        self.d[u]='visited'
        for v in self.Adj[u]:
            if self.d[v] is None:
                self.forests[-1].append(v)
                self.DFS_visit(v)
        self.vetex_order.insert(0,u)
    def transpose(self):
        AdjNew=[[] for u in self.Adj]
        for u in self.V:
            for v in self.Adj[u]:
                AdjNew[v].append(u)
        return AdjNew

def simplest_same_SCC_CC(Adj):
    G=Graph(Adj)
    G.DFS()
    V_in_order=G.vetex_order
    AdjT=G.transpose()
    GT=Graph(AdjT,V_in_order)
    GT.DFS()

    AdjSCC=compute_GSCC(AdjT,GT.forests)
    VSCC=range(len(AdjSCC))  
    AdjSimple=[ [] for i in G.V ]
    for i in VSCC:
        prev=-1
        for u in GT.forests[i]:
            if prev!=-1:
                AdjSimple[prev].append(u)
            prev=u
        if len(GT.forests[i])>=2:
            AdjSimple[GT.forests[i][-1]].append(GT.forests[i][0])
    for u in VSCC:
        if AdjSCC[u]!=[]:
            v=AdjSCC[u][0]
            AdjSimple[GT.forests[u][0]].append(GT.forests[v][0])
    return AdjSimple

def compute_GSCC(AdjT,Forests):
    VSCC=range(len(Forests))
    AdjSCC=[ [] for i in VSCC ]
    s=[None]*len(Adj) #map indicate that which SCC a vetex belongs to
    for i in VSCC:
        for u in Forests[i]:
            s[u]=i
    for i in VSCC:
        for u in Forests[i]:
            for v in AdjT[u]:
                if AdjSCC[s[v]]==[] or AdjSCC[s[v]][-1]!=i:
                    if s[v]!=i: #no i,i in AdjSCC
                        AdjSCC[s[v]].append(i) #升序排列
    return AdjSCC

if __name__=='__main__':
    Adj=[[2],[0,3],[1,3,4],[5],[5,6],[3,7],[4,7],[7]]
    print 'Adj:', Adj
    AdjSimple=simplest_same_SCC_CC(Adj)
    print 'AdjSimple:', AdjSimple

